package com.mxw.算法之美.a18动态规划;

import static jdk.nashorn.internal.objects.NativeMath.min;

/**
 * @author Administrator
 * @create 2024/8/10 11:05
 */
public class a02莱温斯坦距离 {

    /**
     * 允许增加，删除，替换字符，三个编辑操作。
     *
     *
     * 可以删除 a[i]，然后递归考察 a[i+1]和 b[j];可以删除 b[j]，然后递归考察 a[i]和 b[j+1];
     * 可以在 a[i]前面添加一个跟 b[j]相同的字符，然后递归考察 a[i]和 b[j+1];
     * 可以在 b[j]前面添加一个跟 a[i]相同的字符，然后递归考察 a[i+1] 和 b[j];
     * 可以将 a[i]替换成 b[j]，或者将 b[j]替换成 a[i]，然后递归考察 a[i+1]和 b[j+1]。
     */

    public int lwstDp(char[] a, char[] b) {
        int n = a.length;
        int m = a.length;
        int[][] minDis = new int[n][m];
        // 初始化第0行：a[0...0]与b[0...j]的编辑距离
        for (int j = 0; j < m; j++) {
            if (a[0] == b[j]) {
                minDis[0][j] = j;
            } else if (j != 0) {
                minDis[0][j] = minDis[0][j - 1] + 1;
            } else {
                minDis[0][j] = 1;
            }
        }

        // 初始化第0列：a[0...i]与b[0...0]的编辑距离
        for (int i = 0; i < n; i++) {
            if (a[i] == b[0]) {
                minDis[i][0] = i;
            } else if (i != 0) {
                minDis[i][0] = minDis[i - 1][0] + 1;
            } else {
                minDis[i][0] = 1;
            }
        }

        // 按行填表
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (a[i] == b[j]) {
                    minDis[i][j] = min(minDis[i - 1][j] + 1,
                            minDis[i][j - 1] + 1,
                            minDis[i - 1][j - 1]
                    );
                } else {
                    minDis[i][j] =min(minDis[i - 1][j] + 1,
                            minDis[i][j - 1] + 1,
                            minDis[i - 1][j - 1]+1
                    );
                }
            }
        }
        return minDis[n - 1][m - 1];
    }


    public int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }


}
